package com.company.array;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/sort-array-by-parity-ii/
 * @date 2019/11/15 10:44
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
 *
 * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
 *
 * 你可以返回任何满足上述条件的数组作为答案。
 */
public class SortArrayByParityII {

    public static void main(String[] args) {
        int[] ints = sortArrayByParityII(new int[]{4, 2, 5, 7});
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    public static int[] sortArrayByParityII(int[] A) {
        Queue<Integer> q0 = new LinkedList<>();
        Queue<Integer> q1 = new LinkedList<>();

        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                q0.add(A[i]);
            } else {
                q1.add(A[i]);
            }
        }

        for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) {
                A[i] = q0.poll();
            } else {
                A[i] = q1.poll();
            }
        }

        return A;
    }

}

